package 城市任务;

/**
 * 有n个城市，城市从1到n进行编号。小美最初住在k号城市中。在接下来的m天里，小美每天会收到一个任务，她可以选择完
 * 成当天的任务或者放弃该任务。第i天的任务需要在ci号城市完成，如果她选择完成这个任务，若任务开始前她恰好在ci号城
 * 市，则会获得ai的收益；若她不在c号城市，她会前往c号城市，获得bi的收益。当天的任务她都会当天完成，任务完成后，
 * 她会留在该任务所在的ci号城市直到接受下一个任务。如果她选择放弃任务，她会停留原地，且不会获得收益。小美想知道，
 * 如果她合理地完成任务，最大能获得多少收益？
 *
 * 输入描述
 * 第一行三个正整数n，m和k，表示城市数量，总天数，初始所在城市。
 * 第二行为m个整数c1, c2...cm，其中ci表示第i天的任务所在地点为ci
 * 第三行为m个整数a1, a2...am，其中ai表示完成第i天任务且地点不变的收益。
 * 第四行为m个整数b1, b2...bm，其中bi表示完成第i天的任务且地点改变的收益。
 * 1<=k,ci<=n<=3e4
 * 1<=m<=3e4
 * 0<=ai,bi<=1e9
 *
 * 输出描述
 * 输出一个整数，表示小美合理完成任务能得到的最大收益。
 *
 * input:
 * 3 5 1
 * 2 1 2 3 2
 * 9 6 2 1 7
 * 1 3 0 5 2
 *
 * output:
 * 13
 */

/**
 * 作者：王悟空
 * 链接：https://www.nowcoder.com/discuss/1038729?channel=-1&source_id=discuss_terminal_nctrack&trackId=undefined
 * 来源：牛客网
 *
 * 先考虑一个自顶向下的dp，考虑函数f(i, k)，表示从第i个任务开始，当前所在位置为k可以得到的最大收益。不难写出，一共有3种情况：
 *
 * 不完成这个任务，直接选择f(i+1, k)
 * 完成这个任务，且c[i]==k，那么此时贡献为f(i+1, k)+a[i]
 * 完成这个任务，且c[i]!=k，那么此时贡献为f(i+1, c[i])+b[i]
 * 选大的即可，可以写出如下代码：
 *
 * 1
 * 2
 * 3
 * 4
 * 5
 * 6
 * 7
 * 8
 * 9
 * 10
 * 11
 * 12
 * 13
 * 14
 * n, m, k = list(map(int, input().split()))
 * c = list(map(int, input().split()))
 * a = list(map(int, input().split()))
 * b = list(map(int, input().split()))
 *
 * @lru_cache(None)
 * def f(i, k):
 *     if i == m: return 0
 *     if c[i] == k: return f(i+1, k) + a[i]
 *     return max(
 *         f(i + 1, k),
 *         f(i + 1, c[i]) + b[i]
 *     )
 * print(f(0, k))
 * 因为n和m都是3e4，上面这个代码复杂度显然无法全部通过。现在考虑优化：
 *
 * 假设现在位置为k，当前任务所在地为c[i]。c[i]==k很好考虑，直接加上即可。如果c[i]!=k呢？我们需要考虑的是从某一个非k的位置转移过来。
 *
 * 注意，c[i]!=k时，我们只需要找一个非k的位置转移过来即可，并不需要考虑从哪个位置过来。而且无论从哪个位置转移过来，假设是j位置，贡献都是 上一次到达j位置的最大贡献+b[i]。那么我们只需要找到最大的上一次到达j位置的最大贡献。
 *
 * 我们可以维护一个数组pre，pre[i]表示上次到达i位置可以获得的最大价值，利用这个数组，我们可以构造一版，假设当前位置为c[i]：pre[c[i]]=max(pre[c[i]], max{pre[j]+b[i] for j in range(1,n+1) if j!=c[i]} )
 *
 * 但是仍然不够，遍历pre仍然是一个n^2的过程，我们需要继续优化。可以发现，上面的pre[j]和i是无关的。我们每次转移的时候，只需要找到最大的pre[j]即可。但是如果单纯维护一个pre[j]，有可能j和c[i]是相等的，可能造成转移出问题。那么我们只需要维护2个最大的pre[j]，这样可以保证一定有一个值和c[i]不相等，最终达成一个时间复杂度O(n)的解法。
 *
 * 复制代码
 * 1
 * 2
 * 3
 * 4
 * 5
 * 6
 * 7
 * 8
 * 9
 * 10
 * 11
 * 12
 * 13
 * 14
 * 15
 * 16
 * 17
 * 18
 * 19
 * 20
 * 21
 * 22
 * 23
 * 24
 * 25
 * 26
 * 27
 * 28
 * 29
 * 30
 * 31
 * 32
 * 33
 * n, m, k = list(map(int, input().split()))
 * c = list(map(int, input().split()))
 * a = list(map(int, input().split()))
 * b = list(map(int, input().split()))
 *
 * h = [(0, i) for i in range(1, n + 1)]
 * pre = [-1] * (n + 1)
 * pre[k] = 0
 * v1 = (0, k) # 最大
 * v2 = (0, 0) # 次大
 *
 * for i in range(m):
 *     v = 0
 *     # 直通
 *     if pre[c[i]] != -1:
 *         v = max(v, pre[c[i]] + a[i])
 *
 *     if c[i] != v1[1]:
 *         v = max(v, v1[0] + b[i])
 *     elif c[i] != v2[1]:
 *         v = max(v, v2[0] + b[i])
 *
 *     pre[c[i]] = max(pre[c[i]], v)
 *
 *     if v > v1[0]:
 *         if c[i] == v1[1]:
 *             v1 = (v, c[i])
 *         else:
 *             v1, v2 = (v, c[i]), v1
 *     elif v > v2[0]:
 *         v2 = (v, c[i])
 *
 * print(max(pre))
 */
public class Main {
}
